import collections


class Solution(object):
    def generateSentences(self, synonyms, text):
        """
        :type synonyms: List[List[str]]
        :type text: str
        :rtype: List[str]
        """
        d = {}
        d_index = {}
        index = 0
        edges = collections.defaultdict(list)
        for pair in synonyms:
            if pair[0] not in d:
                d[pair[0]] = index
                d_index[index] = pair[0]
                index += 1
            if pair[1] not in d:
                d[pair[1]] = index
                d_index[index] = pair[1]
                index += 1
        n = len(d)
        p = [i for i in range(n)]

        def find(x):
            if x == p[x]:
                return x
            else:
                p[x] = find(p[x])
                return p[x]

        def union(x, y):
            rootx = find(x)
            rooty = find(y)
            if rootx != rooty:
                if rootx < rooty:
                    p[rooty] = rootx
                else:
                    p[rootx] = rooty

        for pair in synonyms:
            union(d[pair[0]], d[pair[1]])

        for i in range(n):
            p[i] = find(p[i])
            edges[p[i]].append(d_index[i])
        for key in edges:
            edges[key].sort()

        text = text.split(' ')
        m = len(text)
        now_words = collections.deque()
        out = []

        def search(i):
            if i == m:
                out.append(' '.join(now_words))
            else:
                if text[i] not in d:
                    now_words.append(text[i])
                    search(i + 1)
                    now_words.pop()
                else:
                    for word in edges[p[d[text[i]]]]:
                        now_words.append(word)
                        search(i + 1)
                        now_words.pop()
        search(0)
        return out


data = Solution()
# synonyms = [["happy", "joy"], ["sad", "sorrow"], ["joy", "cheerful"]]
# text = "I am happy today but was sad yesterday"
# print(data.generateSentences(synonyms, text))
synonyms = [["c", "d"], ["a", "b"], ["b", "c"], ["d", "e"]]
text = "a b"
print(data.generateSentences(synonyms, text))
